package dynamicProgramming.knapsack;

/**
 * @author zxc
 * @date 2023/01/26 09:13
 **/
/**
 * 题目 ：分割等和子集
 * 题目详情 ：
 * 给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
 *
 * 提示：
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 */
public class CanPartition02 {
    /**
     * 思路 ：
     * 迭代方法 ：来实现判断是否能够将数组分成元素和相等的两个部分
     * ===》 问题转换 ：即，若是要将数组分成元素和相等的两个部分的话，即需要该nums数组中的元素填满容量为 sum / 2的背包;
     * （需要注意的是，sum所存储的是nums数组中所有元素值之和;）
     *
     * 状态转移方程 ：
     * （1）假设f(i,j)为前i个物品中选择若干个是否能够填满容量为j的背包;
     * （2）若是第i个物品不加入到容量为j背包的话，则f(i,j) = f(i-1,j);
     * （3）若是第i个物品加入到容量为j背包的话，则f(i,j) = f(i-1,j - nums[i]);
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        // 求nums数组中数组值的和;
        for (int num : nums) {
            sum += num;
        }
        // 特殊情况 ：若是数组中元素和sum不为偶数的话，即代表其不能够分割成等和子集;
        if(sum % 2 != 0){
            return false;
        }
        // 若是数组中元素和sum为偶数的话，即每个等和子集的值为 sum / 2;
        return isDivided(nums , sum / 2);

    }
    // 判断当前数组nums中的元素是否能够被分割成等和子集;
    private boolean isDivided(int[] nums, int target) {
        // 即，使用辅助数组temp来存储f(i,j)结果（即，是否能够从前i个物品中选择若干个填满容量为j的背包）
        // （1）若是选择将第i个加入到背包的话，即 f(i-1,j-nums[i]);
        // （2）若是选择不将第i个加入到背包中，则f(i-1,j);
        boolean[] temp = new boolean[target + 1];
        // 特殊情况 ：当背包容量为0的话，即不选nums数组中任何元素就能够满足;
        temp[0] = true;
        // 由于temp数组中,temp[i][0]和temp[0][j]所存储的皆是 a.背包容量为0的情况;b.物品个数为0的情况;
        for(int i = 1; i <= nums.length; i++){
            /**
             * （1）若是按照从左到右的顺序填充表格的话，f(i-1,j)随时有可能被后续的f(i + x,j)被调用，去求解f(i + x,j);
             * （2）若是按照从右到左的顺序填充表格的话，f(i,j)计算完之后就不会被后续的f(i - x,j)所调用;
             * ===> 所以选择使用从右到左的顺序进行填充temp二维数组;
             */
            for(int j = target; j > 0; j--){
                // 一般情况 ：若是选择将第i个加入到背包的话，即 f(i-1,j-nums[i]);
                if(!temp[j] && j >= nums[i - 1]){
                    // 判断 ：若是不将第i个物品加入到背包中，也能够满足前i个物品中能够选择若干个填满容量为j的背包;
                    // ===》 即，直接返回true即可
                    temp[j] = temp[j - nums[i - 1]];
                }
            }
        }
        return temp[target];
    }
}
